Adjacency Matrix — Costs

• Space: The matrix always requires $O(n^2)$ space, regardless of the number of edges. This is ideal for dense graphs but wasteful for sparse ones.
• Adjacency Test: The primary strength of a matrix. Checking for an edge $(u,v)$ is a direct lookup at `A[u][v]`, which is an $O(1)$ operation.
• List Neighbors: To find all neighbors of a vertex $u$, one must scan its entire corresponding row in the matrix, taking $O(n)$ time.
• Add / Remove Edge: Adding or removing an edge is as simple as setting a matrix cell to 1 or 0, making it a fast $O(1)$ operation.